package kyssion.leetcode.num101_150;

import kyssion.leetcode.util.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class code103_二叉树锯齿层次遍历 {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> listList = new ArrayList<>();
        if (root == null) {
            return listList;
        }
        List<TreeNode> old = new ArrayList<>();
        List<TreeNode> newNode = new ArrayList<>();
        old.add(root);
        boolean need = true;
        boolean before = true;
        while (old.size() > 0) {
            List<Integer> list = new ArrayList<>();
            if (before == need) {
                for (TreeNode treeNode : old) {
                    if (treeNode != null) {
                        list.add(treeNode.val);
                        if (treeNode.left != null) {
                            newNode.add(treeNode.left);
                        }
                        if (treeNode.right != null) {
                            newNode.add(treeNode.right);
                        }
                    }
                }
            } else {
                for (int index = old.size() - 1; index >= 0; index--) {
                    if (old.get(index) != null) {
                        list.add(old.get(index).val);
                        if (before) {
                            if (old.get(index).right != null) {
                                newNode.add(old.get(index).right);
                            }
                            if (old.get(index).left != null) {
                                newNode.add(old.get(index).left);
                            }
                        } else {
                            if (old.get(index).left != null) {
                                newNode.add(old.get(index).left);
                            }
                            if (old.get(index).right != null) {
                                newNode.add(old.get(index).right);
                            }
                        }
                    }
                }
                before = need;
            }
            need = !need;
            listList.add(list);
            old = newNode;
            newNode = new ArrayList<>();
        }
        return listList;
    }


    public List<List<Integer>> zigzagLevelOrder2(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        genLevelOrder(root, list, 0);
        return list;
    }

    public void genLevelOrder(TreeNode root, List<List<Integer>> list, int index) {
        if (root == null)
            return;
        if (index >= list.size()) {
            list.add(new ArrayList<Integer>());
            list.get(index).add(root.val);
        } else {
            if (index % 2 == 0) {
                list.get(index).add(root.val);
            } else {
                list.get(index).add(0, root.val);
            }
        }
        genLevelOrder(root.left, list, index + 1);
        genLevelOrder(root.right, list, index + 1);

    }
}
